1. Field of the Invention
This invention relates to priority encoders and, more particularly, to priority encoders, called rotating priority encoders, in which the request signals are arranged in a priority circle whose basepoint can be rotated at will.
2. Prior Art
A computer system often has limited facilities available at any one time to serve all of its users. Consequently, it is necessary to give priority to certain users according to some predetermined priority protocol using a priority encoder.
A conventional priority encoder is an electronic digital logic circuit which has a number of input request terminals which are connected to input request lines from particular users and which accept request signals from those users. When the signal on an input request line associated with a particular user is in its active state, it indicates that the particular user associated with that request line is requesting service. A conventional priority encoder circuit also has a number of output terminals which provide an output code word, called an index number, which is a binary-coded word identifying which of the active input request lines has highest priority. If a request signal is not present on the input request line with the highest priority, the input request line with next highest priority is selected as having the highest priority, and so forth.
It is desirable in a computing system that no active request for service be ignored forever and that, on the average, no input request line be favored more than any other input request line. This is accomplished, for example, by using what is called a rotating priority encoder. This concept is visualized by imagining the input request terminals for a priority encoding system to be arranged in a circle and by establishing one of the terminals as a base point. A priority encoder is then used to find the first active input request line which is located in a given direction (for example, counterclockwise) around the circle from the given base point. The base point is periodically moved, or rotated, from one input request line to another around the circle to insure that no individual input request is ever ignored and that on the average each input request is equally favored.
FIG. 1 shows a conventional approach to a system 10 for implementing a rotating priority encoder. A conventional barrel shifter 12 receives input request signals I on N input request lines 14. A k-bit index-shift code word, called the index-shift code X, is received on k signal lines 15. X controls the number of bit positions through which the bits on the N input request lines 14 are rotated before being presented at the output terminals 0 of the barrel shifter 12. Note that the index-shift code has to be able to represent the values from 0 through N-1. Hence N can be no greater than 2 raised to the k power. N output lines 16 connected to the output terminals of the barrel shifter are then connected to the N input terminals of a priority encoder circuit 18. The function of this circuit 18 is to determine which of the rotated request lines 16 are active and which active line has the highest priority. The active rotated input request line with the highest priority is defined as the active line with the lowest index code word. Information identifying the highest priority active rotated line is presented as a k-bit binary code word V on k signal lines 20. An adder 22 is used to adjust V to compensate for the rotation of the input request signals caused by the barrel shifter 12. This is accomplished by adding the amount of shift provided by the index-shift code X to the code of the highest priority rotated request line.
A primary disadvantage of the conventional barrel-shifter approach is that it requires use of a barrel shifter. A barrel shifter is a complex circuit which takes a number of circuit devices to implement. In addition, for a large number of request lines, there is no convenient way to form a composite barrel shifter, which accepts a large number of input lines, by combining several barrel shifters having smaller numbers of input lines.
A number of cross-connections are required between the several component barrel shifters. Fast composite barrel shifter systems require one multiplexer circuit for each output line. This results in a circuit which is fast but very complex. Alternatively, a slower composite barrel shifter system can be produced using shift-registers, instead of barrel shifters and multiplexers. The shift-register implementation results in a circuit which is somewhat less complex but much slower in speed.
Another approach to implementing a rotating priority encoder for N input request lines is to use N priority encoders, one for each of the N possible base points and a multiplexer. Each one of the N priority encoders has the priority request signals connected to its input terminals in a different order, corresponding to the N available base points. In a rotating priority encoder, a base point is defined as the input request line which has been assigned the highest priority. Consequently, for this approach, each of the N priority encoders has a different request signal connected to its highest priority input terminal. For a given base point, the lower priority input request signals to a priority encoder are connected to input terminals having correspondingly lower priority. The lowest priority input request signals are wrapped and connected to the lowest priority input terminals of a particular priority encoder. The multiplexer for this system has N groups of input terminals, with each group connected to one of the index code word outputs from one of the N priority encoders. The index code word for the highest priority request is selected by the multiplexer from whichever priority encoder is associated with the desired priority base point. The base point is indicated as an index code word by the multiplexer. The base point index code word is periodically adjusted to shift the base point of the request lines. This approach implements a rotating priority encoder which is fast and easily expandable, but it requires a large number of circuits to implement. It also requires a number of cross-connections between each input request line and each of the N priority encoders.